#include <iostream>
#include <vector>
using namespace std;

void SelectionSort1 (vector<int>& v) {
	int min_index = 0;
	int len = v.size();
	for(int i = 0; i < len; i++) {
		min_index = i;
		for(int j = i + 1; j < len; j++) {
			if(v[j] < v[min_index])
				min_index = j;
		}
		swap(v[i], v[min_index]);
	}
}

//二元选择排序
void SelectionSort2 (vector<int>& v) {
	int min_index = 0;
	int max_index = 0;
	int range = v.size();
	for(int i = 0; i < range; i++) {
		min_index = i;
		max_index = i;
		for(int j = i+1; j< range; j++) {
			if(v[j] < v[min_index])
				min_index = j;
			if(v[j] > v[max_index])
				max_index = j;
		}
		swap(v[i], v[min_index]);
		swap(v[max_index], v[--range]);
	}
}

int main() {
	vector<int> v{1,4,3,2,7,9,5,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	//SelectionSort1(v);
	SelectionSort2(v);
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}

/*
排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：
当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

不稳定算法，时间复杂度为 O(n^2); 只使用有限个变量，空间复杂度 O(1)。
*/